package xiaomin.demo.algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/*
给定 一个 没有 重叠 的 区间 序列， 现 插入 一个 新的 区间 到 该 序列 中， 要求 维持 没有 重叠 的 情况。
假设 该 序列 存放 的 区间 是 有序 的。 区间 定义 如 题目“ 重叠 区间 个数”。

陈东锋. 进军硅谷:程序员面试揭秘 (技术移民参考手册) (p. 69). 电子工业出版社. Kindle 版本.

思路：
1.构造新的区间列表 newInterList
2.构建Point列表,排序
3.遍历Point列表,如果有重叠区间,合并区间,复制到newInterList,如果不重叠,直接复制到newInterList
 */
public class Lesson08 {

    static class Interval{
        int start;
        int end;
        Interval(int a,int b){
            start=a;
            end=b;
        }

        @Override
        public String toString() {
            return "Interval{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }

    static class Point implements Comparable<Point>{
        int value;
        int type;
        Point(int v,int t){
            this.value=v;
            this.type=t;
        }

        public int compareTo(Point o) {
            if(this.value>o.value){
                return 1;
            }
            else if(this.value<o.value){
                return -1;
            }
            else {
                //类型不同 star end值相同 则 end更大，在后面
                // 1        5      5      10
                // start   start  end     end
                if(o.type!=this.type){
                    System.out.println("相等"+this.value);
                    if(this.type==1) return 1;
                    else return -1;
                }
                else {
                    return 0;
                }
            }
        }
    }

    public static void run() {
        //构建4个区间
        Interval[] intervals = new Interval[6];
        intervals[0] = new Interval(2, 5);
        intervals[1] = new Interval(6, 10);
        intervals[2] = new Interval(11, 20);
        intervals[3] = new Interval(30, 40);
        intervals[4] = new Interval(5, 6);
        intervals[5] = new Interval(10, 11);

        //声明点列表
        List<Point> pointList=new ArrayList<Point>();
        for(Interval interval:intervals){
            pointList.add(new Point(interval.start,0));
            pointList.add(new Point(interval.end,1));
        }

        //对点排序
        Collections.sort(pointList);

        //记录遍历过程中打开的区间数,用于合并区间
        int openCount=0;

        List<Interval> newInterList=new ArrayList<Interval>();

        for(Point p:pointList){
            if(p.type==0){//区间打开
                if(openCount==0){//新的区间
                    newInterList.add(new Interval(p.value,0));
                }
                openCount++;
            }
            else {//区间关闭
                if(openCount==1) {//区间结束
                    newInterList.get(newInterList.size() - 1).end = p.value;
                }
                openCount--;
            }
        }

        //输出新的区间
        for(Interval interval: newInterList){
            System.out.println(interval.toString());
        }
    }
}
